/**
 * Convert Sorted Array to Binary Search Tree
 * 
 * Given an array where elements are sorted in ascending order, 
 * convert it to a height balanced BST.
 * 
 * 方法：因为已经有序了，所以每次取中间的节点为根节点，依次递归建立
 */
package No101_200.No101_110.ConvertSortedArraytoBinarySearchTree_108;
/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年2月27日 下午6:12:51 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {
	
    public TreeNode sortedArrayToBST(int[] nums) {
        return create(nums,0,nums.length-1);
    }
    public TreeNode create(int[] nums,int start,int end){
        if(nums.length == 0){
            return null;
        }
        int mid = (start + end)/2;
        TreeNode root = new TreeNode(nums[mid]);
        if(start<=mid-1){
            root.left = create(nums,start,mid-1);
        }
        if(mid+1<=end){
            root.right = create(nums,mid+1,end);
        }
        return root;
    } 

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
}
